package com.arron.algorithm.leetcodetop100.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class N皇后 {
    char QUEEN_STR = 'Q';
    char NULL_STR = '.';
    List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {

        List<String> list = new ArrayList<>();
        res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(NULL_STR);
            }
            list.add(sb.toString());
        }

        solveNQueens(list, 0);

        return res;
    }

    public void solveNQueens(List<String> list, int row) {

        if (row == list.size()) {
            res.add(new ArrayList<>(list));
            return;
        }
        char[] chars = list.get(row).toCharArray();
        for (int j = 0; j < chars.length; j++) {
            if (!valid(list, row, j)) {
                continue;
            }

            StringBuilder sb = new StringBuilder(list.get(row));
            sb.setCharAt(j, QUEEN_STR);
            list.set(row, sb.toString());

            solveNQueens(list, row + 1);

            sb.setCharAt(j, NULL_STR);
            list.set(row, sb.toString());

        }


    }

    private boolean valid(List<String> list, int row, int col) {
        if (row == 0) {
            return true;
        }
        //判断同一列的正上方
        for (int i = 0; i < row; i++) {
            char c = list.get(i).charAt(col);
            if ( c != NULL_STR) {
                return false;
            }

        }

        //判断左上角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0 && col > 0; ) {
            char c = list.get(i).charAt(j);
            if (c != NULL_STR) {
                return false;
            }
            i--;
            j--;
        }

        //判断右上角
        for (int i = row - 1, j = col + 1; i >= 0 && j < list.get(0).length(); ) {
            if (list.get(i).charAt(j) != NULL_STR) {
                return false;
            }
            i--;
            j++;
        }

        return true;
    }


    public static void main(String[] args) {
        N皇后 n = new N皇后();
        n.solveNQueens(4);

        System.out.println(n.res);
    }

}
